Methods and apparatus for multi-carrier communication with variable channel bandwidth are disclosed, where the time frame structure and the OFDM symbol structure are invariant and the frequency-domain signal structure is flexible. In one embodiment, a mobile station, upon entering a geographic area, uses a core-band to initiate communication and obtain essential information and subsequently switches to full operating bandwidth of the area for the remainder of the communication. If the mobile station operates in a wide range of bandwidths, the mobile station divides the full range into sub-ranges and adjusts its sampling frequency and its FFT size in each sub-range.