Verification of the identities of parties participating in network-based communication, such as telephone communication, including SMS/text communication, email communication and the like is provided. Communication identifiers (IDs) (e.g., telephone numbers, email addresses or the like) are verified as being associated with one or more communication parties and, in response, a verified communication (ID) database is established. The verified communication ID database is relied upon when a user/communication is selecting a communication ID as an address for an impending communication or receiving a communication for determining whether the communication ID is verifiably associated with a known communication party. If the communication ID is determined to be verifiably associated with a known communication party, a visual or audible output may be provided on the user's device or within the communication that indicates that the communication ID is verifiably associated with the known communication party.