We study nonlinear vacuum electrodynamics in a first-order formulation proposed by Plebanski. By applying a Dirac constraint analysis, we derive an effective Hamiltonian, together with the equations of motion. We show that there exists a large class of potentials for which the effective Hamiltonian is bounded from below, while at the same time possessing stationary points in which the field strength acquires a nonzero vacuum expectation value. The associated spontaneous breaking of Lorentz symmetry can in principle be detected by coupling the model to a suitable external current, or to gravity. We show that the possible vacua can be classified in four classes. We study some of their properties, using explicit examples for illustration.