This paper investigates the issue of spatial-temporal opportunity detection for spectrum-heterogeneous cognitive radio networks, where at a given time secondary users (SUs) at different locations may experience different spectrum access opportunities. Most prior studies address either spatial or temporal sensing in isolation and explicitly or implicitly assume that all SUs share the same spectrum opportunity. However, this assumption is not realistic and the traditional non-cooperative sensing (NCS) and cooperative sensing (CS) schemes are not very effective in a more realistic setting considering the heterogeneous spectrum availability among SUs. We define new performance metrics to guide the spatial-temporal opportunity detection and propose a two-dimensional sensing (TDS) framework to improve the opportunity detection performance, which exploits correlations in time and space simultaneously by effectively fusing sensing results in a spatial-temporal sensing window. Furthermore, in terms of maximum interference constrained transmission power (MICTP), we classify the spatial opportunities for SUs into three groups: black, grey, and white, and propose a TDS-based distributed power control scheme to further improve the spectrum utilization by exploiting both grey and white spectrum opportunities. The effectiveness of the proposed scheme is demonstrated through in-depth numerical simulations under a variety of scenarios.