Two-dimensional alloys of carbon and nitrogen draw strong interest due to prospective applications in nanomechanical and optoelectronic devices. The stability of these chemical structures can vary greatly as a function of chemical composition and structure. The present study employs hybrid density functional theory and reactive molecular dynamics simulations to elucidate how many nitrogen atoms can be incorporated into the graphene sheet without destroying it. We conclude that (1) the C/N = 56:29 structure and all nitrogen-poorer structures maintain stability at 1000 K; (2) the stability suffers greatly in the presence of N-N bonds; and (3) distribution of electron density depends heavily on the structural pattern in the N-doped graphene. Our calculations support the experimental efforts aimed at production of highly N-doped graphene and generate important insights into the mechanisms of tuning graphene mechanical and optoelectronic properties. The theoretical prediction can be tested directly by chemical synthesis.