Coarse-grained molecular dynamics simulations are used to explore the interaction with a phospholipid bilayer of the voltage sensor (VS) domain and the S4 helix from the archaebacterial voltage-gated potassium (Kv) channel KvAP. Multiple 2-mus self-assembly simulations reveal that the isolated S4 helix may adopt either interfacial or transmembrane (TM) locations with approximately equal probability. In the TM state, the insertion of the voltage-sensing region of S4 is facilitated via local bilayer deformation that, combined with side chain "snorkeling," enables its Arg side chains to interact with lipid headgroups and water. Multiple 0.2-mus self-assembly simulations of the VS domain are also performed, along with simulations of MscL and KcsA, to permit comparison with more "canonical" integral membrane protein structures. All three stably adopt a TM orientation within a bilayer. For MscL and KcsA, there is no significant bilayer deformation. In contrast, for the VS, there is considerable local deformation, which is again primarily due to the lipid-exposed S4. It is shown that for both the VS and isolated S4 helix, the positively charged side chains of S4 are accommodated within the membrane through a combination of stabilizing interactions with lipid glycerol and headgroup regions, water, and anionic side chains. Our results support the possibility that bilayer deformation around key gating charge residues in Kv channels may result in "focusing" of the electrostatic field, and indicate that, when considering competing models of voltage-sensing, it is essential to consider the dynamics and structure of not only the protein but also of the local lipid environment.