We develop a theory of toroidal vertex algebras and their modules, and we give a conceptual construction of toroidal vertex algebras and their modules. As an application, we associate toroidal vertex algebras and their modules to toroidal Lie algebras.