We propose a solitary wave model for small scale magnetic structures observed in the solar wind and more recently in the Voyager 1 observations of the heliosheath. The model is based on the recent, fully nonlinear theory of solitary waves by McKenzie et al. (2001, 2004). Our solutions i.e., magnetic holes, humps, trains of holes and humps, are strongly nonlinear (70 to 80% change in the magnetic field at the centre), propagate at large angles (>600) to the mean magnetic field and are well approximated by Gaussians. The structures are almost pressure balanced with an anti-correlation between the magnetic field and the plasma density, and no change in the magnetic vector across the structure. These features are consistent with observations of magnetic structures in the heliosheath.