The extraction of nucleic acids from a given environment marks a crucial and essential starting point in any molecular investigation. Members of Halococcus spp. are known for their rigid cell walls, and are thus difficult to lyse and could potentially be overlooked in an environment. Furthermore, the lack of a suitable lysis method hinders subsequent molecular analysis. The effects of six different DNA extraction methods were tested on Halococcus hamelinensis, Halococcus saccharolyticus and Halobacterium salinarum NRC-1 as well as on an organic rich, highly carbonated sediment from stromatolites spiked with Halococcus hamelinensis. The methods tested were based on physical disruption (boiling and freeze/thawing), chemical lysis (Triton X-100, potassium ethyl xanthogenate (XS) buffer and CTAB) and on enzymatic lysis (lysozyme). Results showed that boiling and freeze/thawing had little effect on the lysis of both Halococcus strains. Methods based on chemical lysis (Triton X-100, XS-buffer, and CTAB) showed the best results, however, Triton X-100 treatment failed to produce visible DNA fragments. Using a combination of bead beating, chemical lysis with lysozyme, and thermal shock, lysis of cells was achieved however DNA was badly sheared. Lysis of cells and DNA extraction of samples from spiked sediment proved to be difficult, with the XS-buffer method indicating the best results. This study provides an evaluation of six commonly used methods of cell lysis and DNA extraction of Halococcus spp., and the suitability of the resulting DNA for molecular analysis.