This paper address advertising in ubiquitous media environments by empirically discussing challenges suggested in previous research. We have performed 15 interviews, 4 workshops and 3 brainstorming sessions with publishers and advertisiers. Our findings agree with previous research but also point out several additional challeging issues. We conclude by suggesting that the publishers are well suited to take on the role as pervasive service providers and identify four specific

challenges related to that role: 1) How to develop models to produce and make use of consumer information dynamically over time in a ubiquitous media environment?; 2) How to adjust advertising to consumer preferences, i.e. advertising on consumer terms?; 3) In what ways can advertising be integrated with services/content adjusted to context? and 4) How to create an arena for building relations between consumers and advertisers as well as between advertisers?