Software-based self-test (SBST) is emerging as a promising technology for enabling at-speed testing of high-speed embedded processors testing in an SoC system. For SBST, test routine development or generation can base on deterministic and random methodology. The deterministic test methodology develops the test program for a pipeline processor using the information abstracted from its architecture model, RTL descriptions, and gate-level net-list for different types of processor circuits. The random test methodology tries to make the pseudo-exhaustive testing possible using random instructions or patterns. The proposed methodology improves coverage for structural faults using both deterministic and random development of the test code. Not only can the deterministic test program test lots of faults using very small code size, but also the random test program can help detect some of the faults that the deterministic test program is difficult to test. We demonstrated the feasibility of the proposed methodology by the achieved fault coverage, test program size, and testing cycle count on a complex pipeline processor core. Comparisons with previous work are also made. Experimental results show its potential as an effective method for practical use.