In this paper, we present a coexistence protocol design for a coexistence information service to provide coexistence solutions among dissimilar or independently operated autonomous decision-making networks in a wireless communication environment over, specifically but not limited to, TV white space (TVWS) frequency bands. The designed coexistence protocol for the coexistence information service has three main functionalities: (1) To collect basic information of subscribed TVWS networks; (2) To support generating neighbor lists for the TVWS networks based on the geography information and/or propagation parameters; (3) To provide necessary information for TVWS networks to make coexistence decisions. Both theoretical analysis and simulation results show that the designed coexistence information service ensures harmonious communications among dissimilar networks and is able to achieve coexistence over an area with the limited number of available channels in white space.