This work presents the results of research toward designing an instruction set extension dedicated to Global Navigation Satellite System (GNSS) baseband processing. The paper describes the state-of-the-art techniques of GNSS receiver implementation. Their advantages and disadvantages are discussed. Against this background, a new versatile instruction set extension for GNSS baseband processing is presented. The authors introduce improved mechanisms for instruction set generation focused on multi-channel processing. The analytical approach used by the authors leads to the introduction of a GNSS-instruction set extension (ISE) for GNSS baseband processing. The developed GNSS-ISE is simulated extensively using PC software and field-programmable gate array (FPGA) emulation. Finally, the developed GNSS-ISE is incorporated into the first-in-the-world, according to the authors' best knowledge, integrated, multi-frequency, and multi-constellation microcontroller with embedded flash memory. Additionally, this microcontroller may serve as an application processor, which is a unique feature. The presented results show the feasibility of implementing the GNSS-ISE into an embedded microprocessor system and its capability of performing baseband processing. The developed GNSS-ISE can be implemented in a wide range of applications including smart IoT (internet of things) devices or remote sensors, fostering the adaptation of multi-frequency and multi-constellation GNSS receivers to the low-cost consumer mass-market.