In this paper, we propose an innovative self-organizing medium access control mechanism for a distributed cognitive radio network (CRN) in which utilization is maximized by minimizing the collisions and missed opportunities. This is achieved by organizing the users of the CRN in a queue through a timer and user ID and providing channel access in an orderly fashion. To efficiently organize the users in a distributed, ad hoc network with less overhead, we reduce the sensing period through parallel sensing wherein the users are divided into different groups and each group is assigned a different portion of the primary spectrum band. This consequently augments the number of discovered spectrum holes which then are maximally utilized through the self-organizing access scheme. The combination of two schemes augments the effective utilization of primary holes to above 95%, even in impasse situations due to heavy primary network loading, thereby achieving higher network throughput than that achieved when each of the two approaches are used in isolation. By efficiently combining parallel sensing with the self-organizing MAC (PSO-MAC), a synergy has been achieved that affords the gains which are more than the sum of the gains achieved through each one of these techniques individually. In an experimental scenario with 50% primary load, the network throughput achieved with combined parallel sensing and self-organizing MAC is 50% higher compared to that of parallel sensing and 37% better than that of self-organizing MAC. These results clearly demonstrate the efficacy of the combined approach in achieving optimum performance in a CRN.