Let $G$ be a discrete group with a generating submonoid $P$ such that $P\cap P^{-1}=\{e\}$. There is a partial order on $G$ where $x\leq y$ if and only if $x^{-1}y\in P$. The pair $(G,P)$ is quasi-lattice ordered if all $x, y\in G$ with a common upper bound in $P$ have a least upper bound in $P$. For example, the Baumslag-Solitar groups \[G=\langle a, b : ab^c = b^da \rangle\] with submonoid $P$ generated by $a$ and $b$ are quasi-lattice ordered groups. Other examples can be found in Thompson's group $F$ (this is a bit of a tease). $C^*$-algebras of quasi-lattice ordered groups were introduced by Nica in 1992. After defining two $C^*$-algebras associated to quasi-lattice orders, I will discuss some of their properties, with a focus on what we call amenability.