The rapidly increasing availability of healthcare data from multiple heterogeneous sources has spearheaded the adoption of data-driven approaches for improved clinical research, decision making, and patient management. The patient healthcare data are usually longitudinal and can be expressed as medical event sequences, where the events include clinical diagnosis, medications, laboratory reports, etc. Because healthcare data has both longitudinal and heterogeneous attributes, analyzing healthcare data is an inherently difficult challenge. In this paper, we propose a hospital readmission prediction method using temporal phenotypes, namely the Tephe. Specifically, each patient's medical event sequence is first represented by a temporal graph, which captures temporal relationships of the medical events in each event sequence and makes the raw data more intuitive. Based on graph pattern mining, we define more significant frequent subgraphs as temporal phenotypes. This enables us to better understand the disease evolving patterns and treatment approach. In addition, we designed an improved greedy algorithm to find the optimal expression coefficient of frequent subgraphs for each patient. Finally, based on the optimal expression coefficient of the frequent subgraph, random forests are used to perform prediction tasks. The experimental results show that our proposed method is more accurate in the prediction tasks compared with the baselines.