A necessary and sufficient condition for a smooth, compact 4-manifold to admit the structure of a Stein domain was given many years ago by Eliashberg, in terms of the existence of a certain kind of handle decomposition. In practice it is not always clear whether such a handle decomposition exists, even on a 4-manifold that is topologically very simple. We describe examples of 4-dimensional 2-handlebodies with a single 2-handle that do not obviously satisfy Eliashberg’s criteria yet still admit a Stein structure, and also examples of contractible 4-manifolds that do not admit any Stein structure despite satisfying various necessary conditions. The latter examples have bearing on a conjecture of Gompf asserting that no Brieskorn homology sphere admits a pseudoconvex embedding in complex 2-space.