insert a NOT NULL column to an existing table

The error message is quite descriptive, try:

ALTER TABLE MyTable ADD Stage INT NOT NULL DEFAULT '-';

As an option you can initially create Null-able column, then update your table column with valid not null values and finally ALTER column to set NOT NULL constraint:

ALTER TABLE MY_TABLE ADD STAGE INT NULL
GO
UPDATE MY_TABLE SET <a valid not null values for your column>
GO
ALTER TABLE MY_TABLE ALTER COLUMN STAGE INT NOT NULL
GO

Another option is to specify correct default value for your column:

ALTER TABLE MY_TABLE ADD STAGE INT NOT NULL DEFAULT '0'

---

UPD: Please note that answer above contains GO which is a must when you run this code on Microsoft SQL server. If you want to perform the same operation on Oracle or MySQL you need to use semicolon ; like that:

ALTER TABLE MY_TABLE ADD STAGE INT NULL;
UPDATE MY_TABLE SET <a valid not null values for your column>;
ALTER TABLE MY_TABLE ALTER COLUMN STAGE INT NOT NULL;

Other SQL implementations have similar restrictions. The reason is that adding a column requires adding values for that column (logically, even if not physically), which default to NULL. If you don't allow NULL, and don't have a default, what is the value going to be?

Since SQL Server supports ADD CONSTRAINT, I'd recommend Pavel's approach of creating a nullable column, and then adding a NOT NULL constraint after you've filled it with non-NULL values.

If you aren't allowing the column to be Null you need to provide a default to populate existing rows. e.g.

ALTER TABLE dbo.YourTbl ADD
    newcol int NOT NULL CONSTRAINT DF_YourTbl_newcol DEFAULT 0

On Enterprise Edition this is a metadata only change since 2012