In several influential works, Melrose has studied examples of non-compact manifolds M(0) whose large scale geometry is described by a Lie algebra of vector fields V subset of Gamma(M; TM) on a compactification of M(0) to a manifold with corners M. The geometry of these manifolds-called ``manifolds with a Lie structure at infinity{''}-was studied from an axiomatic point of view in a previous paper of ours. In this paper, we define and study an algebra Psi(1,0V)(infinity)(M(0)) of pseudodifferential operators canonically associated to a manifold M(0) with a Lie structure at infinity V subset of Gamma(M; TM). We show that many of the properties of the usual algebra of pseudodifferential operators on a compact manifold extend to the algebras that we introduce. In particular, the algebra Psi(10,V)(infinity)(M(0)) is a ``microlocalization{''} of the algebra Diff(V)({*})(M) of differential operators with smooth coefficients on M generated by V and C(infinity)(M). This proves a conjecture of Melrose (see his ICM 90 proceedings paper).