We always use surrogate keys when creating new fact and dimension tables. We had some old tables and ETL code around that didn't use them, and we haven't got around to retrofitting. As far as I can tell, surrogate keys started to turn up around 1997 - 98, though I really haven't done an exhaustive search. Kimball didn't talk about them in his earlier book - The Data Warehouse Toolkit, 1996. But they are in his Lifecycle Toolkit, 1st edition, 1998. I think they were mentioned in magazine articles before that.