The invention discloses a heuristic service combination method based on recent discovery, comprising the following steps: (1) modeling a service combination problem as a six-tuple Markov decision process; solving the six-tuple Markov decision process by use of a heuristic learning method based on Q-learning to get an optimal strategy; and (3) mapping the optical strategy to a workflow of web services combined. According to the method, the learning experience in the learning process is fully utilized to improve the learning speed, and learning is more efficient.