Random-access channels (RACHs) are designed to establish a connection between the user equipments (UEs) and the network. However, the current long-term evolution (LTE) standard has limitations in providing RACH resources to massive UE connections. If numerous UEs send a connection request simultaneously, it results in severe collisions and significant access delays that degrade system performance. There has been a lot of previous research into controlling this overload; however, there are no proposals to resolve RACH overload issues for mission-critical high-priority (MCHP) UEs in coexisting LTE-based public safety (PS-LTE) and LTE-based marine (LTE-M) networks. Thus, immense interest and practical research are urgently required to resolve the UE initial access problem during the random-access procedure, most importantly when MCHP users exist. In this paper, we propose an efficient mission-critical user priority-based random-access scheme for coexisting PS-LTE and LTE-M networks. Since PS-LTE users have mission-critical service requirements, we give higher priority to PS-LTE UEs when allocating RACH resources in the contention-based random-access (RA) procedure. Our proposed scheme efficiently assigns RA preambles to MCHP UEs in order to avoid preamble collisions when multiple UEs try to access coexisting PS-LTE and LTE-M networks. In this paper, the performance of the proposed scheme is analyzed and evaluated based on the number of successful RACH attempts, the number of collisions, and the access delay. The simulation results show the effectiveness of the proposed scheme. Compared with a conventional random-access scheme, the proposed scheme performs remarkably well by improving the number of successful RACH attempts, reducing the number of collisions, and minimizing the access delay to coexisting PS-LTE and LTE-M networks.