The subject matter described herein includes methods, systems, and computer readable media for providing a NAS node selection function with CN node bearer circuit availability monitoring and availability-based load sharing. According to one aspect, the subject matter described herein includes a method for providing a NAS node selection function. The method includes performing various steps at a NAS node selection function which may be integrated with or separate from a media gateway. The method includes monitoring bearer circuit availability for each of a plurality of CN nodes. The method further includes storing an indication of bearer circuit availability for each of the CN nodes. The method further includes receiving initial layer 3 messages from radio access nodes in response to mobile station activity. The method further includes, in response to the messages, assigning mobile stations to the MSCs in a load-sharing manner using the stored indications of bearer circuit availabilities.