Membrane proteins are frequently present in crowded environments, which favour lateral association and, on occasions, two-dimensional crystallization. To better understand the non-specific lateral association of a membrane protein we have characterized the free energy landscape for the dimerization of a bacterial outer membrane protein, NanC, in a phospholipid bilayer membrane. NanC is a member of the KdgM-family of bacterial outer membrane proteins and is responsible for sialic acid transport in E. coli. Umbrella sampling and coarse-grained molecular dynamics were employed to calculate the potentials of mean force (PMF) for a variety of restrained relative orientations of two NanC proteins as the separation of their centres of mass was varied. We found the free energy of dimerization for NanC to be in the range of [Formula: see text] to [Formula: see text]. Differences in the depths of the PMFs for the various orientations are related to the shape of the proteins. This was quantified by calculating the lipid-inaccessible buried surface area of the proteins in the region around the minimum of each PMF. The depth of the potential well of the PMF was shown to depend approximately linearly on the buried surface area. We were able to resolve local minima in the restrained PMFs that would not be revealed using conventional umbrella sampling. In particular, these features reflected the local organization of the intervening lipids between the two interacting proteins. Through a comparison with the distribution of lipids around a single freely-diffusing NanC, we were able to predict the location of these restrained local minima for the orientational configuration in which they were most pronounced. Our ability to make this prediction highlights the important role that lipid organization plays in the association of two NanCs in a bilayer.