In this paper, we consider the possible types of regular maps of order $2^n$, where the order of a regular map is the order of automorphism group of the map. For $n \le 11$, M. Conder classified all regular maps of order $2^n$. It is easy to classify regular maps of order $2^n$ whose valency or covalency is $2$ or $2^{n-1}$. So we assume that $n \geq 12$ and $2\leq s,t\leq n-2$ with $s\leq t$ to consider regular maps of order $2^n$ with type $\{2^s, 2^t\}$. We show that for $s+t\leq n$ or for $s+t>n$ with $s=t$, there exists a regular map of order $2^n$ with type $\{2^s, 2^t\}$, and furthermore, we classify regular maps of order $2^n$ with types $\{2^{n-2},2^{n-2}\}$ and $\{2^{n-3},2^{n-3}\}$. We conjecture that, if $s+t>n$ with $sComment: 16pages