RNA secondary structure including pseudoknots is computationally difficult to predict. Almost all existing algorithms for optimal pseudoknot prediction entail O(n6) running time and O(n4) memory space even for restricted categories of pseudoknots, making pseudoknot prediction unrealistic for RNA of more than 100 nucleotides. We introduced a new heuristic algorithm mBLAST-PK for RNA pseudoknot prediction that can substantially reduce the computational costs. The new algorithm preprocesses the RNA sequence to find all base pairing regions in a sequence based on a modified BLAST technique. It then non-trivially extends Nussinov folding to calculate the structure including pseudoknots. Our program predicted the RNA pseudoknot structures in bacterial tmRNA sequences at about 81% accuracy. The running time and memory space consumption by the algorithm are both reduced by at least two orders of magnitude, making the task of pseudoknot prediction routine on desktop computers.